package 链表.单向.练习;
//返回链表开始入环的第一个节点。如果链表无环，则返回NULL
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Text_9 {
    public ListNode hasCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
//       确保在移动 fast 指针两步之前，fast 及其下一个节点都不为 null
            fast = fast.next.next;
            slow = slow.next;
            //找到相遇点，退出循环
            if (fast == slow) {
                break;
            }
        }
        //快指针走完，都没有找到相遇点
        if (fast == null || fast.next == null) {
            return null;
        }
        //找进入循环点
//        x = Nc+Y
        fast = head;
        //再次相遇的点就是入口点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 创建环

        Text_9 text9 = new Text_9();
        ListNode listNode = text9.hasCycle(node1);
        System.out.println(listNode.val);
    }
}
